package com.zzh.tree;
//给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
//
// 说明: 叶子节点是指没有子节点的节点。
//
// 示例:
//给定如下二叉树，以及目标和 sum = 22，
//
//               5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \      \
//        7    2      1
//
//
// 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
// Related Topics 树 深度优先搜索
// 👍 387 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
public class No112_hasPathSum {
    public static void main(String[] args) {
        No112Solution solution = new No112Solution();
        boolean b = solution.hasPathSum(TreeNode.initTree(), 5);
        System.out.println(b);
    }
}

class No112Solution {
    private int tar;

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root==null){
            return false;
        }
        tar=sum;//目标值
        return pathSum(root,0);
    }

    public boolean pathSum(TreeNode root, int sum) {
        if (root.right==null&&root.left==null){
            //如果为叶子结点，判断总和是否等于目标值
            return root.val+sum==tar;
        }
        boolean a=false;
        boolean b=false;
        //如果左子结点不为空进行判断
        if (root.right!=null){
            a=pathSum(root.right,sum+root.val);
        }
        if (root.left!=null){
            b=pathSum(root.left,sum+root.val);
        }
        //返回
        return a||b;

    }
}
